The Message Passing Interface (MPI) exposes a partially ordered queue of receive operations to applications. Receive operations for messages may target a particular source process or a wild card receive operation indicates that the message may target any process. Messages are matched in the order in which the receive operations were posted, typically on a per source basis.
Most MPI implementations provide a fully ordered sequential queue. As such, incoming messages search the queue sequentially, thereby leading to lengthy search times when a posted receive queue is long. Some solutions employ a hashing technique to separate out incoming messages that target multiple queues. However, this technique suffers from an overhead in use of a complicated hash. Wild card searching further complicates such techniques.